#include <stdio.h>
#include <string.h>

int length(char* input){
	int index = 0;
	char c = input[index];
	int count = 0;
	while(c != '\0'){
		c = input[index];
		index++;
		count++;
	}
	if(index == 0){
		return 0;
	}	
	return count-1;
}

char* append(char* to, char c){
	int last = length(to);
	to[last] = c;
	to[last + 1] = '\0';
	return to;
}

/**
 *
 */
char* subFirstChar(char* from, char* buffer){
	buffer[0] = '\0';
	int lenFrom = length(from);
	int i;
	int rl = lenFrom-1;
	char restL[rl];
	restL[0] = '\0';
	for( i=1; i < lenFrom; i++ ){
		restL[i-1] = from[i];
		restL[i] = '\0';
	}
	strcpy(buffer,restL);
	return buffer;
}


char* merge(char* left, char* right, char* result){
	 int lenLeft = length(left);
	 int lenRight = length(right);
     while ( lenLeft > 0 || lenRight > 0 ){
        if (lenLeft > 0 && lenRight > 0){
			if ( left[0] <= right[0] ){
				result = append(result, left[0]);
				left = left + 1;
            }else{
 				result = append(result, right[0]);
 				right = right + 1;
            }
        }else if ( lenLeft > 0 ){
 				result = append(result, left[0]);
  				left = left + 1;
        }else if ( lenRight > 0 ){
                result = append(result, right[0]);
				right = right + 1;
        }
        lenLeft = length(left);
	 	lenRight = length(right);
    }
	return result;
}    


char* merge_sort(char* m , char* resultado){
	 int len = length(m);
    if( len <= 1 ){
        return m;
    }else{
		 int middle = (len / 2);
		 char left[middle+1];
		 left[0] = '\0';
		 char right[middle+1];
		 right[0] = '\0';
		 int x;
		 for(x = 0; x < middle; x++){
		   left[x] = m[x];
		   left[x + 1] = '\0';
		 }
		 int i;
		 int rig = 0;
 		 for( i = middle; i < len; i++ ){
			right[rig] = m[i];
			right[rig + 1] = '\0';
			rig++;
		 } 
		char resultadoLeft[length(left)];
		resultadoLeft[0] = '\0';
		char* pResultadoLeft = merge_sort(left, resultadoLeft);
		char resultadoRight[length(right)];
		resultadoRight[0] = '\0';
		char* pResultadoRight = merge_sort(right, resultadoRight);

		int sl = length(pResultadoLeft) + length(pResultadoRight);

		char* res = merge(pResultadoLeft, pResultadoRight, resultado);
		return res;
    }
}


int main (int argc, char **argv){
	char* cadena = "9876543210";
	char resultado[length(cadena)];
	resultado[0] = '\0';
	char* result = merge_sort(cadena, resultado);
	printf("Cadena ordenada: %s \n", result);

}


